package com.wg.other.dbtable;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 凑零钱问题：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：
 *
 * // coins 中是可选硬币面值，amount 是目标金额
 * int coinChange(int[] coins, int amount);
 * 比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
 *
 * 你认为计算机应该如何解决这个问题？显然，就是把所有肯能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币
 */
public class CoinChange {


    public static void main(String[] args) {
        List coins=Arrays.asList(1,2,5);
        int amount=13;
        int[] record=new int[amount+1];
        System.out.println(getMinCoinNum(coins,amount,record));
        System.out.println(getMinCoinNum3(coins,amount));
    }
    /**
     * 1.1、暴力递归  自上而下
     */

    public static Integer getMinCoinNum(List<Integer> coins,int amount){
        Integer res=Integer.MAX_VALUE;
        if(amount==0){
            return 0;
        }
        if(amount<0){
            return -1;
        }
        for (int i = 0; i < coins.size(); i++) {
            //最少硬币数量
            Integer minCoinNum=getMinCoinNum(coins,amount-coins.get(i));
            if (minCoinNum<0){
                continue;
            }
            res=Math.min(res,1+minCoinNum);
        }
        return res;
    }

    /**
     * 2.带备忘录的递归
     */
    public static Integer getMinCoinNum(List<Integer> coins,int amount,int[] record){
        Integer res=Integer.MAX_VALUE;
        if(amount==0){
            return 0;
        }
        if(amount<0){
            return -1;
        }
        if(record[amount]!=0){
            return record[amount];
        }
        for (int i = 0; i < coins.size(); i++) {
            //最少硬币数量
            Integer minCoinNum=getMinCoinNum(coins,amount-coins.get(i),record);
            if (minCoinNum<0){
                continue;
            }
            res=Math.min(res,1+minCoinNum);
        }
        record[amount]=res;
        return res;
    }

    /**
     * 3、dp 数组的迭代解法
     */
    public static Integer getMinCoinNum3(List<Integer> coins,int amount){
        int[] amounts=new int[amount+1];
        amounts[0]=0;
        for (int i = 1; i < amounts.length; i++) {
            amounts[i]=i;//默认最大值i
            for (Integer coin:coins) {
                if(coin >i){
                    continue;
                }
                //比较后最小硬币数
                amounts[i]=Math.min(amounts[i],amounts[i-coin]+1);
            }
        }
        return amounts[amount];
    }


}
